#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 20
#define SWAP(a, b) \
    do { \
        typeof(a) (t); \
        (t) = (a); \
        (a) = (b); \
        (b) = (t); \
    } while(0)


void insert_sort(int arr[], int len);

int main(void)
{
    int arr[N];
    srand(time(NULL));
    int i;

    /* 给数组赋值 */
    for (i = 0; i < N; i++) {
        arr[i] = rand() % 1000;
        printf("%d ", arr[i]);
    }
    printf("\n");

    /* 给数组排序 */
    insert_sort(arr, N);

    for (i = 0; i < N; i++)
        printf("%d ", arr[i]);

    printf("\n");
    return 0;
}

void insert_sort(int arr[], int len)
{
    /* 实现从小到大排序 */
    int i, j, temp;
    for (i = 1; i < len; i++) {
        temp = arr[i];
        // 找位置并后移
        for (j = i - 1; j >= 0; j--) {
            if (temp < arr[j]) 
                arr[j + 1] = arr[j]; // 后移 
            else 
                break; // 找到位置
        }

        arr[j + 1] = temp; // 插入
    }
    printf("\n");
}


